﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace MouldingAndMillwork.SSIS
{
    #region CLASS: OrderedHashList<K, V>
    /// <summary>
    /// The OrderedHashList provides a HashTable-like collection of key-value pairs, but extends
    /// that capability to allow an "order" to be associated with eash key-value pair.  The resulting
    /// key-value-order pairs can be retrieved by key or order, and can be enumerated like a List.
    /// </summary>
    public class OrderedHashList<K, V>
    {
        #region CLASS: OrderedHashListEntry
        private class OrderedHashListEntry
        {
            #region Private Variables
            private readonly K _key;
            private readonly V _value;
            private readonly int _arrivalOrder;
            #endregion

            #region Constructor
            public OrderedHashListEntry(K key, V value, int arrivalOrder)
            {
                this._key = key;
                this._value = value;
                this._arrivalOrder = arrivalOrder;
            }
            #endregion

            #region Public Properties
            public K Key
            {
                get { return this._key; }
            }

            public V Value
            {
                get { return this._value; }
            }

            public int ArrivalOrder
            {
                get { return this._arrivalOrder; }
            }
            #endregion

            #region ToString
            public override string ToString()
            {
                return "[" + this._key.ToString() + "].[" + this._arrivalOrder.ToString() + "]"
                    + ".[" + this._value.ToString() + "]";
            }
            #endregion
        }
        #endregion

        #region Private Variables
        private readonly object _lock = new object();
        private readonly Hashtable _entriesByKey;
        private readonly Hashtable _keysByArrivalOrder;
        private List<K> _keysInArrivalOrder;
        private readonly Hashtable _deletedKeysInArrivalOrder;
        #endregion

        #region Constructor
        public OrderedHashList()
        {
            this._entriesByKey = new Hashtable();
            this._keysByArrivalOrder = new Hashtable();
            this._keysInArrivalOrder = new List<K>();
            this._deletedKeysInArrivalOrder = new Hashtable();
        }
        #endregion

        #region Public Properties
        #region Count
        /// <summary>Returns the number of OrderedHashListEntries contained
        /// in the collection.  This is an O(1) operation.</summary>
        public int Count
        {
            get { lock (this._lock) { return this._entriesByKey.Count; } }
        }
        #endregion

        #region Values
        /// <summary>Returns a complete list of values contained in the
        /// collection.  This is an O(n) operation.</summary>
        public List<V> Values
        {
            get
            {
                List<V> values = new List<V>();
                lock (this._lock)
                {
                    foreach (OrderedHashListEntry entry in this._entriesByKey.Values)
                    {
                        values.Add(entry.Value);
                    }
                }
                return values;
            }
        }
        #endregion
        #endregion

        #region Public Methods
        #region Clear
        /// <summary>Empties the OrderedHashList.  This is an O(1) operation.</summary>
        public void Clear()
        {
            lock (this._lock)
            {
                this._entriesByKey.Clear();
                this._keysByArrivalOrder.Clear();
                this._keysInArrivalOrder.Clear();
                this._deletedKeysInArrivalOrder.Clear();
            }
        }
        #endregion

        #region Add
        /// <summary>Adds a key-value-order to the OrderedHashList.  An exception
        /// will be thrown if the key or arrivalOrder is already present in the collection.
        /// This is an O(1) operation.</summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        /// <param name="arrivalOrder"></param>
        public void Add(K key, V value, int arrivalOrder)
        {
            OrderedHashListEntry entry = new OrderedHashList<K, V>.OrderedHashListEntry(key, value, arrivalOrder);

            lock (this._lock)
            {
                #region Detect and throw exception if the key already exists
                if (this._entriesByKey.Contains(key))
                {
                    if (System.Diagnostics.Debugger.IsAttached)
                    {
                        System.Diagnostics.Debugger.Break();
                    }
                    throw new InvalidOperationException("Key (" + key.ToString() + ") already exists in the collection");
                }
                #endregion
                #region Detect and throw exception if the arrival order already exists
                if (this._keysByArrivalOrder.ContainsKey(arrivalOrder))
                {
                    if (System.Diagnostics.Debugger.IsAttached)
                    {
                        System.Diagnostics.Debugger.Break();
                    }
                    throw new InvalidOperationException("Arrival order (" + arrivalOrder.ToString() 
                        + ") already exists in the collection");
                }
                #endregion
                #region Add the entry
                try
                {
                    this._entriesByKey.Add(key, entry);
                    this._keysByArrivalOrder.Add(entry.ArrivalOrder, entry.Key);
                    this._keysInArrivalOrder.Add(entry.Key);
                }
                #region catch ...
                catch (Exception ex)
                {
                    if (System.Diagnostics.Debugger.IsAttached)
                    {
                        System.Diagnostics.Debugger.Break();
                    }
                    throw new ApplicationException("Unexpected exception in OrderedHashList.Add: "
                        + ex.Message, ex);
                }
                #endregion
                #endregion
            }
        }
        #endregion

        #region Remove
        /// <summary>Removes the entry with the specified key from the collection.
        /// This is an O(log n) operation.</summary>
        /// <param name="key"></param>
        public V Remove(K key)
        {
            V removedItem = default(V);

            lock (this._lock)
            {
                OrderedHashListEntry entry = (OrderedHashListEntry)this._entriesByKey[key];
                if (entry != null)
                {
                    #region Remove the entry
                    try
                    {
                        removedItem = entry.Value;

                        this._entriesByKey.Remove(entry.Key);
                        this._keysByArrivalOrder.Remove(entry.ArrivalOrder);
                        this._deletedKeysInArrivalOrder.Add(entry.Key, true);
                    }
                    #region catch ...
                    catch (Exception ex)
                    {
                        if (System.Diagnostics.Debugger.IsAttached)
                        {
                            System.Diagnostics.Debugger.Break();
                        }
                        throw new ApplicationException("Unexpected exception in OrderedHashList.Remove "
                            + "removing entry from internal structures: " + ex.Message, ex);
                    }
                    #endregion
                    #endregion
                }
            }            

            return removedItem;
        }
        #endregion

        #region ContainsKey
        /// <summary>Determines whether the key is in the OrderedHashList.
        /// This is an O(1) operation.</summary>
        /// <param name="key"></param>
        /// <returns>true if the key can be found in the collection.</returns>
        public bool ContainsKey(K key)
        {
            lock (this._lock)
            {
                return this._entriesByKey.ContainsKey(key);
            }
        }
        #endregion

        #region GetValueAtArrivalOrder
        /// <summary>Returns only the "value" portion of the OrderedHashListEntry at the
        /// specified ordinal position.  This is an O(1) operation.</summary>
        /// <param name="arrivalOrder">The arrival order associated with an entry.</param>
        /// <returns>The value with the specified arrival order, or null/zero if that 
        /// arrival order doesn't exist in the collection.</returns>
        public V GetValueAtArrivalOrder(int arrivalOrder)
        {
            lock (this._lock)
            {
                if (this._keysByArrivalOrder.ContainsKey(arrivalOrder))
                {
                    K key = (K)this._keysByArrivalOrder[arrivalOrder];
                    OrderedHashListEntry entry = (OrderedHashListEntry)this._entriesByKey[key];
                    return entry.Value;
                }
            }
            return default(V);
        }
        #endregion

        #region GetKeyAtArrivalOrder
        /// <summary>Returns the "key" portion of the OrderedHashListEntry at the
        /// specified arrival order position.  This is an O(1) operation.</summary>
        /// <param name="arrivalOrder">The arrival order associated with an entry.</param>
        /// <returns>The key with the specified arrival order, or null/zero if that order
        /// doesn't exist in the collection.</returns>
        public K GetKeyAtArrivalOrder(int arrivalOrder)
        {
            lock (this._lock)
            {
                if (this._keysByArrivalOrder.ContainsKey(arrivalOrder))
                {
                    return (K)this._keysByArrivalOrder[arrivalOrder];
                }
            }
            return default(K);
        }
        #endregion

        #region GetArrivalOrderOfKey
        /// <summary>Returns the arrival order portion of OrderedHashListEntry at the
        /// specified ordinal position.  This is an O(1) operation.</summary>
        /// <param name="key">The key associated with an entry.</param>
        /// <returns>The arrival order of the specified key, or -1 if that order
        /// doesn't exist in the collection.</returns>
        public int GetArrivalOrderOfKey(K key)
        {
            lock (this._lock)
            {
                if (this._entriesByKey.ContainsKey(key))
                {
                    OrderedHashListEntry entry = (OrderedHashListEntry)this._entriesByKey[key];
                    return entry.ArrivalOrder;
                }
            }
            return -1;
        }
        #endregion

        #region GetKeys
        public List<K> GetKeys()
        {
            List<K> keys = new List<K>();
            ArrayList tempKeys = new ArrayList();
            lock (this._lock)
            {
                tempKeys.AddRange(this._entriesByKey.Keys);
            }
            foreach (K key in tempKeys)
            {
                keys.Add(key);
            }
            return keys;
        }

        /// <summary>Returns a list of keys that have arrival orders between to numbers.
        /// This is an O(log n) operation.</summary>
        /// <param name="fromArrivalOrder">The arrival order to start from (inclusive).</param>
        /// <param name="toArrivalOrder">The arrival order to end at (inclusive).</param>
        /// <returns>A List of keys whose order values fall within the given range.</returns>
        public List<K> GetKeys(int fromArrivalOrder, int toArrivalOrder)
        {
            List<K> keys = new List<K>();

            lock (this._lock)
            {
                try
                {
                    if (this._entriesByKey.Count > 0)
                    {
                        int fromIndex;
                        int toIndex;
                        #region Find approximate start and end (may not be exact)
                        try
                        {
                            fromIndex = Math.Max(0, this.IndexOfArrivalOrder(fromArrivalOrder, true) - 1);
                            toIndex = Math.Min(this.IndexOfArrivalOrder(toArrivalOrder, true) + 1, 
                                this._keysInArrivalOrder.Count - 1);
                        }
                        #region catch ...
                        catch (Exception ex)
                        {
                            if (System.Diagnostics.Debugger.IsAttached)
                            {
                                System.Diagnostics.Debugger.Break();
                            }
                            throw new ApplicationException("Unexpected exception in OrderedHashList.GetKeys "
                                + "determining start and end positions to retrieve: " + ex.Message, ex);
                        }
                        #endregion
                        #endregion

                        #region Refine start and end indexes to be inclusive
                        try
                        {
                            bool indexReady = false;
                            while ((!indexReady) && (fromIndex < this._keysInArrivalOrder.Count))
                            {
                                K key = this._keysInArrivalOrder[fromIndex];
                                OrderedHashListEntry entry = (OrderedHashListEntry)this._entriesByKey[key];
                                if (entry.ArrivalOrder >= fromArrivalOrder)
                                {
                                    indexReady = true;
                                }
                                else
                                {
                                    fromIndex++;
                                }
                            }
                            indexReady = false;
                            while ((!indexReady) && (toIndex >= 0))
                            {
                                K key = this._keysInArrivalOrder[toIndex];
                                OrderedHashListEntry entry = (OrderedHashListEntry)this._entriesByKey[key];
                                if (entry.ArrivalOrder <= toArrivalOrder)
                                {
                                    indexReady = true;
                                }
                                else
                                {
                                    toIndex--;
                                }
                            }
                            toIndex = Math.Max(toIndex, fromIndex);
                        }
                        #region catch ...
                        catch (Exception ex)
                        {
                            if (System.Diagnostics.Debugger.IsAttached)
                            {
                                System.Diagnostics.Debugger.Break();
                            }
                            throw new ApplicationException("Unexpected exception in OrderedHashList.GetKeys "
                                + "refining start and end positions to retrieve: " + ex.Message, ex);
                        }
                        #endregion
                        #endregion

                        #region Retrieve set
                        try
                        {
                            if (fromIndex < this._keysInArrivalOrder.Count)
                            {
                                keys.AddRange(this._keysInArrivalOrder.GetRange(fromIndex, toIndex - fromIndex + 1));
                            }
                        }
                        #region catch ...
                        catch (Exception ex)
                        {
                            if (System.Diagnostics.Debugger.IsAttached)
                            {
                                System.Diagnostics.Debugger.Break();
                            }
                            throw new ApplicationException("Unexpected exception in OrderedHashList.GetKeys "
                                + "retrieving keyset: " + ex.Message, ex);
                        }
                        #endregion
                        #endregion
                    }
                }
                #region catch ...
                catch (Exception ex)
                {
                    if (System.Diagnostics.Debugger.IsAttached)
                    {
                        System.Diagnostics.Debugger.Break();
                    }
                    throw ex;
                }
                #endregion
            }

            return keys;
        }
        #endregion

        #region Indexer
        /// <summary>Indexer that returns the value of the OrderedHashListEntry
        /// specified by the given key.  This is an O(1) operation.</summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public V this[K key]
        {
            get
            {
                lock (this._lock)
                {
                    if (this._entriesByKey.ContainsKey(key))
                    {
                        OrderedHashListEntry entry = (OrderedHashListEntry)this._entriesByKey[key];
                        return entry.Value;
                    }
                }
                return default(V);
            }
        }
        #endregion
        #endregion

        #region Private Helpers
        #region IndexOfArrivalOrder (and helper)
        private int IndexOfArrivalOrder(int arrivalOrder, bool closeEnough)
        {
            // already locked by caller
            if ((arrivalOrder == 0) && (closeEnough))
            {
                return 0;
            }
            else if (this._keysInArrivalOrder.Count == 0)
            {
                return -1;
            }
            else
            {
                this.PurgeDeletedKeysInArrivalOrder();

                int depth = 0;
                int index = -1;
                index = this.IndexOfArrivalOrder_Helper(depth, arrivalOrder, closeEnough, 0, 
                    this._keysInArrivalOrder.Count - 1);
                return index;
            }
        }

        private int IndexOfArrivalOrder_Helper(int depth, int arrivalOrder, bool closeEnough, 
            int fromIndex, int toIndex)
        {
            // already locked by caller

            #region Detect stack overflows
            if (depth > 32)
            {
                if (System.Diagnostics.Debugger.IsAttached)
                {
                    System.Diagnostics.Debugger.Break();
                }
                throw new ApplicationException("Stack overflow condition detected in "
                    + "OrderedHashList.IndexOfArrivalOrder_Helper.");
            }
            #endregion

            int testIndex = (fromIndex + toIndex) / 2;
            K testKey;
            try
            {
                testKey = this._keysInArrivalOrder[testIndex];
            }
            #region catch ...
            catch (Exception ex)
            {
                if (System.Diagnostics.Debugger.IsAttached)
                {
                    System.Diagnostics.Debugger.Break();
                }
                throw new ApplicationException("OrderedHashList.IndexOfArrivalOrder_Helper had an exception "
                    + "retrieving index " + testIndex.ToString() + " from key list (count: "
                    + this._keysInArrivalOrder.Count.ToString() + "): " + ex.Message, ex);
            }
            #endregion

            OrderedHashListEntry entry = (OrderedHashListEntry)this._entriesByKey[testKey];
            if (entry.ArrivalOrder == arrivalOrder)
            {
                return testIndex;
            }
            else if (fromIndex == toIndex)
            {
                if (closeEnough)
                {
                    return fromIndex;
                }
                else
                {
                    return -1;
                }
            }
            else
            {
                if (entry.ArrivalOrder > arrivalOrder)
                {
                    return this.IndexOfArrivalOrder_Helper(depth + 1, arrivalOrder, closeEnough, 
                        fromIndex, Math.Max(fromIndex, testIndex - 1));
                }
                else
                {
                    return this.IndexOfArrivalOrder_Helper(depth + 1, arrivalOrder, closeEnough, 
                        Math.Min(testIndex + 1, toIndex), toIndex);
                }
            }
        }
        #endregion

        #region PurgeDeletedKeysInArrivalOrder
        private void PurgeDeletedKeysInArrivalOrder()
        {
            // Already locked by caller
            if (this._deletedKeysInArrivalOrder.Count > 0)
            {
                List<K> purgedKeysInOrder = new List<K>();
                for (int index = 0; index < this._keysInArrivalOrder.Count; index++)
                {
                    if (!this._deletedKeysInArrivalOrder.ContainsKey(this._keysInArrivalOrder[index]))
                    {
                        purgedKeysInOrder.Add(this._keysInArrivalOrder[index]);
                    }
                }
                this._keysInArrivalOrder = purgedKeysInOrder;
                this._deletedKeysInArrivalOrder.Clear();
            }
        }
        #endregion
        #endregion
    }
    #endregion
}
